package class07;

// 从左往右尝试
public class Code03_Knapsack {
    /**
     * @param w   重量
     * @param v   价值
     * @param bag 最大重量
     * @return 不超重bag 前提下获得最大价值
     */
    static int maxValue(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length == 0 || v.length == 0) {
            return 0;
        }
        return process(w, v, bag, 0);
    }

    // 当前考虑到index  index 之后可以自由选择，并且不能超过bag
    static int process(int[] w, int[] v, int rest, int index) {

        // 如果bag==0 ,可以装货物，有可能货物重量为0但是价值大于0,所以此处使用<0 判断

        // 两个条件不能改顺序
        if (rest < 0) {
            return -1;
        }
        if (index == w.length) {
            return 0;
        }
        // 不要当前货物价值
        int p1 = process(w, v, rest, index + 1);


        // 要当前货物最大价值
        /**
         * int p2 = v[index]+process(w, v, rest - w[index], index + 1); 此操作不对，如果只有一个货物并且重量大于bag ,
         * 并且bag<0 则return 0;这样就会导致 拿到这个超过bag 的重量的货物
         * 所以修改无效解，然后判断拿了货物 所剩容量如果不是-1 就拿货物
         */


        int p2 = 0;

        int next = process(w, v, rest - w[index], index + 1);
        if (next != -1) {
            p2 = v[index] + next;
        }

        return Math.max(p1, p2);

    }


    static int dp(int[] w, int[] v, int bag) {
        int n = w.length;
        // 第一列表示index 0-n;第二列 rest负数-bag
        int[][] dp = new int[n + 1][bag + 1];

        for (int index = n - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {

                int p1 = dp[index + 1][rest];
                int p2 = 0;
                int next = rest - w[index] >= 0 ? dp[index + 1][rest - w[index]] : -1;

                if (next != -1) {
                    p2 = v[index] + next;
                }
                dp[index][rest] = Math.max(p1, p2);
            }

        }


        return dp[0][bag];// 返回值参考process 入参


    }

    public static int dp1(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = 0;
                int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
                if (next != -1) {
                    p2 = v[index] + next;
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }

    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7, 3, 1, 7};
        int[] values = {5, 6, 3, 19, 12, 4, 2};
        int bag = 15;
        System.out.println(maxValue(weights, values, bag));
        System.out.println(dp(weights, values, bag));
    }
}








